package com.zh.note.leetcode.string;

/**
 * 151. 反转字符串中的单词
 * <p>
 * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
 * <p>
 * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
 * <p>
 * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
 * <p>
 * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
 */
public class LC_151_reverseWords {

    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        //1. 移除多余空格
        char[] newChars = removeExtraSpaces(chars);
        //2.整个字符串反转
        reverse(newChars, 0, newChars.length - 1);
        //3.单词反转
        reverseEachWord(newChars);
        return new String(newChars);
    }

    /**
     * 单词内字符串反转
     *
     * @param chars
     */
    private void reverseEachWord(char[] chars) {
        int start = 0;
        //end <= s.length() 这里的 = ，是为了让 end 永远指向单词末尾后一个位置，这样 reverse 的实参更好设置
        for (int end = 0; end <= chars.length; end++) {
            // end 每次到单词末尾后的空格或串尾,开始反转单词
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }

    /**
     * 移除多余空格
     *
     * @param chars
     * @return
     */
    private char[] removeExtraSpaces(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            if (chars[fast] != ' ') {
                if (slow != 0) {
                    //在用 slow 加空格。 除第一个单词外，单词末尾要加空格
                    chars[slow] = ' ';
                    slow++;
                }
                //fast 遇到空格或遍历到字符串末尾，就证明遍历完一个单词了
                while (fast < chars.length && chars[fast] != ' ') {
                    chars[slow] = chars[fast];
                    fast++;
                    slow++;
                }

            }
        }
        //必须要重新创建一个数组，愿数组的移除元素的后长度是不变的
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow);
        return newChars;
    }

    /**
     * 字符串反转
     *
     * @param ch
     * @param i
     * @param j
     */
    private void reverse(char[] ch, int i, int j) {
        for (; i < j; i++, j--) {
            char temp = ch[i];
            ch[i] = ch[j];
            ch[j] = temp;
        }
    }
}
